package stringFind

func KMPSearch(main, pattern string) int {
	n := len(main)
	m := len(pattern)
	if n < m {
		return -1
	}
	nexts := GetNexts(pattern)
	j := 0
	for i := 0; i <= n-1; i++ {
		for j > 0 && main[i] != pattern[j] {
			j = nexts[j-1] + 1
		}
		if main[i] == pattern[j] {
			if j == m-1 {
				return i - m + 1
			}
			j++
		}
	}

	return -1
}

func GetNexts(pattern string) []int {
	m := len(pattern)
	nexts := make([]int, m)
	// init
	for i := range nexts {
		nexts[i] = -1
	}
	for i := 1; i <= m-2; i++ {
		j := nexts[i-1]
		for pattern[j+1] != pattern[i] && j >= 0 {
			j = nexts[j]
		}
		if pattern[j+1] == pattern[i] {
			j++
		}
		nexts[i] = j
	}
	return nexts
}
